﻿#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<string>
#include<vector>
#include<list>
#include<algorithm>
#include <stack>
#include<queue>
#include<map>
#include <iostream>
#include <string>
using namespace std;
//int main()
//{
//	int arr[] = { 1, 2, 3 };
//	for (auto e : arr) {
//		cout << e << " ";
//	}
//	return 0;
//}
//typedef char* pstring;
//int main()
//{
//	const pstring p1=0;    // 编译成功还是失败？
//	const pstring* p2;   // 编译成功还是失败？
//	return 0;
//
// }
//int TestAuto()
//{
//	return 10;
//}
//int main()
//{
//	int a = 10;
//	auto b = a;
//	auto c = 'a';
//	auto d = TestAuto();
//	cout << typeid(b).name() << endl;
//	cout << typeid(c).name() << endl;
//	cout << typeid(d).name() << endl;
//	//auto e; 无法通过编译，使用auto定义变量时必须对其进行初始化
//	return 0;
//}
//int main()
//{
//    int x = 10;
//    auto a = &x;
//    auto* b = &x;
//    auto& c = x;
//    cout << typeid(a).name() << endl;
//    cout << typeid(b).name() << endl;
//    cout << typeid(c).name() << endl;
//    *a = 20;
//    *b = 30;
//    c = 40;
//    return 0;
//}
//#define ADD(x,y) ((x)+(y))
//int& Add(int a, int b);
// int main()
//{
//    int ret = Add(1, 2);
//    /*Add(3, 4);*/
//    cout << "Add(1, 2) is :" << ret << endl;
//    return 0;
//}
//int ADD(int x = 1, int y = 2, int z = 3)
//{
//	return x * y * z;
//}
//int ADD(double x = 1.0, double y = 2.0, double z = 3.0)
//{
//	return x +y + z;
//}
//int main()
//{
//	int add = ADD(2.0);
//	cout << add << endl;
//	return 0;
//}
//class Time
//{
//public:
//    Time()
//    {
//        _hour = 1;
//        _minute = 1;
//        _second = 1;
//        
//            注意：在编译器生成的默认拷贝构造函数中，内置类型是按照字节方式直接拷贝的，而自定
//            义类型是调用其拷贝构造函数完成拷贝的。
//            4. 编译器生成的默认拷贝构造函数已经可以完成字节序的值拷贝了，还需要自己显式实现吗？
//            当然像日期类这样的类是没必要的。那么下面的类呢？验证一下试试？
//    }
//    Time(const Time& t)
//    {
//        _hour = t._hour;
//        _minute = t._minute;
//        _second = t._second;
//        cout << "Time::Time(const Time&)" << endl;
//    }
//private:
//    int _hour;
//    int _minute;
//    int _second;
//};
//class Date
//{
//private:
//    // 基本类型(内置类型)
//    int _year = 1970;
//    int _month = 1;
//    int _day = 1;
//    // 自定义类型
//    Time _t;
//};
//int main()
//{
//    Date d1;
//
//    // 用已经存在的d1拷贝构造d2，此处会调用Date类的拷贝构造函数
//    // 但Date类并没有显式定义拷贝构造函数，则编译器会给Date类生成一个默认的拷贝构造函数
//        Date d2(d1);
//    return 0;
//}
//class Stack
//{
//
//};
//class A
//{
//public:
//	/*A(int a = 0)
//		:_a(a)
//	{
//		cout << "A(int a = 0)" << endl;
//	}*/
//	A(int a)
//		:_a(a)
//	{
//		cout << "A(int a = 0)" << endl;
//	}
//private:
//	int _a;
//};
//
//class B
//{
//public:
//	// 初始化列表：对象的成员定义的位置
//	B(int a, int ref)
//		:_ref(ref)
//		, _n(1)
//		, _x(2)
//		, _aobj(a)
//	{
//		//_n = 0;
//		//_ref = ref;
//	}
//
//private:
//	// 声明
//	A _aobj;	  // 没有默认构造函数
//
//	// 特征：必须在定义的时候初始化
//	int& _ref;	  // 引用
//	const int _n; // const
//
//	int _x = 1;  // 这里1是缺省值，缺省值是给初始化列表的
//};
//int main()
//{
//	B b(10,2);
//	return 0;
//}
//class A
//{
//public:
//	static A GetStackObj()
//	{
//		A aa;
//		return aa;
//	}
//
//	static A* GetHeapObj()
//	{
//		return new A;
//	}
//private:
//	A()
//	{}
//
//private:
//	int _a1 = 1;
//	int _a2 = 2;
//};
//
//int main()
//{
//	//static A aa1;   //  静态区
//	//A aa2;          //  栈 
//	//A* ptr = new A; //  堆
//	A::GetStackObj();
//	A::GetHeapObj();
//
//	return 0;
//}
//class A
//{
//public:
//    A() { ++_scount; }
//    A(const A& t) { ++_scount; }
//    ~A() { --_scount; }
//    static int GetACount() { return _scount; }
//private:
//    static int _scount;
//};
//
//int A::_scount = 0;
//
//void TestA()
//{
//    cout << A::GetACount() << endl;
//    A a1, a2;
//    cout << A::GetACount() << endl;
//    A a3(a1);
//    cout << A::GetACount() << endl;
//}
//int main()
//{
//    TestA();
//}

//class A
//{
//public:
//    A(int a = 0)
//        :_a(a)
//    {
//        cout << "A(int a)" << endl;
//    }
//
//    A(const A& aa)
//        :_a(aa._a)
//    {
//        cout << "A(const A& aa)" << endl;
//    }
//
//    A& operator=(const A& aa)
//    {
//        cout << "A& operator=(const A& aa)" << endl;
//
//        if (this != &aa)
//        {
//            _a = aa._a;
//        }
//
//        return *this;
//    }
//
//    ~A()
//    {
//        cout << "~A()" << endl;
//    }
//private:
//    int _a;
//};
//void Func1(A aa)
//{
//
//}
//
//void Func2(const A& aa)
//{
//
//}
//
//A Func3()
//{
//    A aa;
//    return aa;
//}
//
//A& Func4()
//{
//    static A aa;
//    return aa;
//}
//
//A Func5()
//{
//    A aa;
//    return aa;
//}
//
//// 20:25
//int main()
//{
//    A ra1 = Func5(); // 拷贝构造+拷贝构造 ->优化为拷贝构造
//    cout << "==============" << endl;
//    A ra2;
//    ra2 = Func5();
//
//    //A aa1;
//    //Func1(aa1); // 不会优化
//
//    //Func1(A(1)); // 构造+拷贝构造 ->优化为构造
//    //Func1(1);    // 构造+拷贝构造 ->优化为构造
//
//    //A aa2 = 1;  // 构造+拷贝构造 ->优化为构造
//
//
//    return 0;
//}

//int main()
//{
//    int a = 1;
//    const int b = 2;
//    cout << &a << endl;
//    cout << &b << endl;
//
//
//    return 0;
//}

//int main()
//{
//    // C
//    int* p1 = (int*)malloc(sizeof(int));
//    free(p1);
//
//    // CPP
//    int* p2 = new int;
//    delete p2;
//
//    // C
//    int* p3 = (int*)malloc(sizeof(int)*10);
//    free(p3);
//
//    // CPP 申请10个int的数组
//    int* p4 = new int[10];
//    delete[] p4;
//
//    // CPP 申请一个数组，初始化为10
//    int* p5 = new int(10);
//    delete p5;
//
//    int* p6 = new int[10]{1,2,3};
//    delete[] p6;
//
//    return 0;
//}

//struct ListNode
//{
//    int _val;
//    struct ListNode* _next;
//
//    ListNode(int x)
//        :_val(x)
//        , _next(NULL)
//    {}
//};
//
//struct ListNode* BuyListNode(int x)
//{
//    // 单纯开空间
//    struct ListNode* newnode = (struct ListNode*)malloc(sizeof(struct ListNode));
//    // 检查
//    newnode->_next = NULL;
//    newnode->_val = x;
//
//    return newnode;
//}
//
//int main()
//{
//    struct ListNode* n1 = BuyListNode(1);
//    struct ListNode* n2 = BuyListNode(2);
//    struct ListNode* n3 = BuyListNode(3);
//
//    // 开空间+调用构造函数初始化
//    ListNode* nn1 = new ListNode(1);
//    ListNode* nn2 = new ListNode(2);
//    ListNode* nn3 = new ListNode(3);
//
//    return 0;
//}
//int main()
//{
//	// 21：18继续
//	string url = "ftp://www.baidu.com/?tn=65081411_1_oem_dg";
//	// http://www.baidu.com/?tn=65081411_1_oem_dg
//	//string url = "https://legacy.cplusplus.com/reference/string/string/";
//	// 协议  域名  资源名
//	size_t pos1 = url.find("://");
//	string protocol;
//	if (pos1 != string::npos)
//	{
//		protocol = url.substr(0, pos1);
//	}
//	cout << protocol << endl;
//
//	string domain;
//	string uri;
//
//	size_t pos2 = url.find('/', pos1 + 3);
//	if (pos2 != string::npos)
//	{
//		domain = url.substr(pos1 + 3, pos2 - (pos1 + 3));
//		uri = url.substr(pos2 + 1);
//	}
//	cout << domain << endl;
//	cout << uri << endl;
//
//
//	// test.cpp.zip
//	// test.tar.zip
//
//	return 0;
//}

//int** generate(int numRows, int* returnSize, int** returnColumnSizes) 
//{
//
//}
//class A
//{
//public:
//    void Print()
//    {
//        cout << "Print()" << endl;
//    }
//private:
//    int _a;
//};
//int main()
//{
//    A* p = nullptr;
//    p->Print();
//    return 0;
//}
 //1.下面程序编译运行结果是？  A、编译报错  B、运行崩溃  C、正常运行
//class A
//{
//public:
//    void PrintA()
//    {
//        cout << _a << endl;
//    }
//private:
//    int _a;
//};
//int main()
//{
//    A* p = nullptr;
//    p->PrintA();
//    return 0;
//}
//class A
//
//{
//
//public:
//
//    A(int a)
//
//        :_a1(a)
//
//        , _a2(_a1)
//
//    {}
//
//
//
//    void Print()
//
//    {
//
//        cout << _a1 << " " << _a2 << endl;
//
//    }
//
//private:
//
//    int _a2;
//
//    int _a1;
//
//};
//int main()
//{
//    A aa(1);
//    aa.Print();
//
//
// 
// 
// 
// 
// 
// 
// 
// }
//class Sum
//{
//public:
//    Sum()
//    {
//        _ret += _i;
//        _i++;
//    }
//
//    static int GetRet()
//    {
//        return _ret;
//    }
//private:
//    static int _i;
//    static int _ret;
//};
//int Sum::_i = 1;
//int Sum::_ret = 0;
//
//class Solution {
//public:
//    int Sum_Solution(int n) {
//        Sum a[n];
//        return Sum::GetRet();
//    }
//};
//
//int main()
//{
//    Solution s;
//    int m;
//    cin >> m;
//    cout << s.Sum_Solution(m) << endl;
//}

//
//using namespace std;
//class Solution {
//public:
//    int evalRPN(vector<string>& tokens) {
//        stack <int> a;
//        for (auto& b : tokens)
//        {
//            if (b == "+")//如何操作str!=char??
//            {
//                int right = a.top();
//                a.pop();
//                int left = a.top();
//                a.pop();
//                a.push(right + left);
//            }
//            else if (b == "-")//如何操作str!=char??
//            {
//                int right = a.top();
//                a.pop();
//                int left = a.top();
//                a.pop();
//                a.push(left - right);
//            }
//            else if (b == "*")//如何操作str!=char??
//            {
//                int right = a.top();
//                a.pop();
//                int left = a.top();
//                a.pop();
//                a.push(right * left);
//            }
//            else if (b == "/")//如何操作str!=char??
//            {
//                int right = a.top();
//                a.pop();
//                int left = a.top();
//                a.pop();
//                a.push(left / right);
//            }
//            else
//            {
//                a.push(stoi(b));
//            }
//
//        }
//        return a.top();
//    }
//};
//int main()
//{
//    Solution s;
//    string b;
//    vector<string> a = { "4", "13", "5", "/", "+" };
//    s.evalRPN(a);
//    return 0;
//}
//
//struct TreeNode {
//    int val;
//    TreeNode* left;
//    TreeNode* right;
//    TreeNode() : val(0), left(nullptr), right(nullptr) {}
//    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
//    TreeNode(int x, TreeNode* left, TreeNode* right) : val(x), left(left), right(right) {}
//};
//
//class Solution {
//public:
//    vector<vector<int>> levelOrder(TreeNode* root) {
//        vector<vector<int>> vv;
//        vector<int> v;
//        queue<TreeNode*> q;
//        int sz = 1;
//        q.push(root);
//        while (sz)
//        {
//            while (sz--)
//            {
//                TreeNode* t = q.front();
//                q.pop();
//                v.push_back(t->val);
//                if (t->left)
//                {
//                    q.push(t->left);
//                }
//                if (t->right)
//                {
//                    q.push(t->right);
//                }
//            }
//            vv.push_back(v);
//            v.clear();
//            sz = q.size();
//
//        }
//        return vv;
//    }
//};
//
//int main()
//{
//    Solution s;
//    
//    return 0;
//}
//

//class Solution {
//public:
//    int myAtoi(string str) {
//        int sign = 1;
//        int ret=0;
//        for (auto a : str)
//        {
//            //if (a == '-')
//            //{
//            //    sign = -1;
//            //}
//            if (a >= '0' && a <= '9')
//            {
//                ret = ret * 10 + 'a' - '0';
//            }
//        }
//        if (str.find('-') != -1)
//        {
//            ret *= -1;
//        }
//        return ret;
//    }
//};




//int main()
//{
//    std::string str("There are two needles in this haystack with needles .");
//    std::string str2("needle");
//
//    // different member versions of find in the same order as above:
//    std::size_t found = str.find(str2);
//    if (found != std::string::npos)
//        std::cout << "first 'needle' found at: " << found << '\n';
//
//    found = str.find("needles are small", found + 1, 8);
//    if (found != std::string::npos)
//        std::cout << "second 'needle' found at: " << found << '\n';
//
//    found = str.find("haystack");
//    if (found != std::string::npos)
//        std::cout << "'haystack' also found at: " << found << '\n';
//
//    found = str.find('.');
//    if (found != std::string::npos)
//        std::cout << "Period found at: " << found << '\n';
//
//    // let's replace the first needle:
//    str.replace(str.find(str2), str2.length(), "preposition");
//    std::cout << str << '\n';
//
//    return 0;
//}

//int firstUniqChar(string s) {
//    int flag = 1;
//    for (int i = 0; i < s.size(); i++)
//    {
//        for (int j = 0; j < s.size(); i++)
//        {
//            if (j != i)
//            {
//                if (s[i] == s[j])
//                    flag = 0;
//                break;
//            }
//        }
//        if (flag == 1)
//            return i;
//        flag = 1;
//    }
//    return -1;
//}
//
////int main()
////{
////	int i;
////	char buffer[256];
////	printf("Enter a number: ");
////	fgets(buffer, 256, stdin);
////	i = atoi(buffer);
////	printf("The value entered is %d. Its double is %d.\n", i, i * 2);
////	return 0;
////}
//
//
//int main()
//{
//    string s = "loveleetcode";
//    cout << firstUniqChar(s);
//}




//
//﻿int main()
//{
//	string a = "hello world";
//
//	string b = a;
//
//	if (a.c_str() == b.c_str())
//
//	{
//
//		cout << "true" << endl;
//
//	}
//
//	else cout << "false" << endl;
//
//	string c = b;
//
//	c = "";
//
//	if (a.c_str() == b.c_str())
//
//	{
//
//		cout << "true" << endl;
//
//	}
//
//	else cout << "false" << endl;
//
//	a = "";
//
//	if (a.c_str() == b.c_str())
//
//	{
//
//		cout << "true" << endl;
//
//	}
//	else cout << "false" << endl;
//
//	return 0;
//
//}



//int main() {
//	string a = "hello world";
//	string b = a;
//
//	if (a.c_str() == b.c_str()) {
//		cout << "true" << endl;
//	}
//	else {
//		cout << "false" << endl;
//	}
//
//	string c = b;
//	c = "";
//
//	if (a.c_str() == b.c_str()) {
//		cout << "true" << endl;
//	}
//	else {
//		cout << "false" << endl;
//	}
//
//	a = "";
//	if (a.c_str() == b.c_str()) {
//		cout << "true" << endl;
//	}
//	else {
//		cout << "false" << endl;
//	}
//
//	return 0;
//}

//int main()
//{
//	string strText = "How are you?";
//	string strSeparator = " ";
//	string strResult;
//	int size_pos = 0;
//	int size_prev_pos = 0;
//	while ((size_pos = strText.find_first_of(strSeparator, size_pos)) != string::npos)
//	{
//
//		strResult = strText.substr(size_prev_pos, size_pos - size_prev_pos);
//
//		cout << strResult << " ";
//
//		size_prev_pos = ++size_pos;
//
//	}
//	if (size_prev_pos != strText.size())
//	{
//
//		strResult = strText.substr(size_prev_pos, size_pos - size_prev_pos);
//
//		cout << strResult << " ";
//
//	}
//	cout << endl;
//	return 0;
//}

//int main() 
//{
//    int a, b;
//    while (cin >> a >> b) { // 注意 while 处理多个 case
//        cout << a + b << endl;
//    }
//    return 0;
//}

//int main() {
//    string a;
//    getline(cin, a);
//    cout << a.size() - a.find_last_of(" ")-1;
//    //// {
//
//    //// }
//
//}


//int main()
//{
//    string s= "A man, a plan, a canal: Panama";
//    for (int i = 0; i < s.size(); i++)
//    {
//        if (s[i] >= 'A' && s[i] <= 'Z')
//        {
//            s[i] += 'a' - 'A';
//        }
//        else if ((s[i] >= '0' && s[i] <= '9') || s[i] >= 'a' && s[i] <= 'z')
//        {
//
//        }
//        else
//        {
//            s.erase(i, 1);
//            i--;
//        }
//            
//    }
//    string s1 = s;
//    reverse(s1.begin(), s1.end());
//    cout <<( s1 == s);
//    return 0;
//    }

//int main()
//{
//    string s = "abcdefg";
//    int k = 2;
//    int K = 2*k;
//    string::iterator b = s.begin();
//    while (K <= s.size()) 
//    {
//        reverse(b,b+k);
//        b += 2 * k;
//        K += 2*k;
//    }
//
//    reverse(b, s.end()<(b+k)?s.end():(b+k));
//    cout << s;
//	return 0;
//}

//int main()
//{
//    string s{ "Let's take LeetCode contest" };
//    int pos = 0;
//    int prpos = 0;
//    string::iterator prit = s.begin();
//    string::iterator it = prit;
//    while ((pos = s.find(" ", pos)) != string::npos)
//    {
//        it += pos-prpos;
//        reverse(prit, it);
//        prit = it + 1;
//        prpos = pos;
//        pos += 1;
//    }
//    reverse(prit, s.end());
//    cout << s;
//	return 0;
//}
//string addStrings(string num1, string num2) {
//    int sm = 0, l1 = num1.size(), l2 = num2.size();
//    string ans = "";
//    while (l1 || l2 || sm)
//    {
//        if (l1)
//            sm += num1[--l1] - '0';
//        if (l2)
//            sm += num2[--l2] - '0';
//        ans = char('0' + sm % 10) + ans;
//        sm /= 10;
//    }
//
//
//    return ans;
//}
//string multiply(string num1, string num2) {
//    int mu = 0, l1 = num1.size() - 1, l2 = num2.size() - 1;
//    string ans = "";
//    string ret = "0";
//    for (int i = l1; i >= 0; i--)
//    {
//        char a = num1[i];
//        for (int j = l2; j >= 0; j--)
//        {
//            char b = num2[j];
//            mu += (b - '0') * (a - '0');
//            ans = char('0' + mu % 10) + ans;
//            mu /= 10;
//        }
//        if(mu)
//            ans = char('0' + mu) + ans;
//        int ct = l1 - i;
//        while (ct--)
//        {
//            ans += '0';
//        }
//        ret = addStrings(ret, ans);
//        ans = "";
//        mu = 0;
//
//    }
//    for(int k = ret.size()-1; k > 0; k--)
//    {
//        if (ret[k] == '0')
//        {
//            ret.erase(k, 1);
//        }
//    }
//    return ret;
//}
//int main()
//{
//    string num1 = "123";
//    string num2 = "0";
//    cout << multiply(num1, num2);
//    return 0;
//}
//
//int main()
//{
//    int numRows = 5;
//    vector<vector<int>> aa;
//
//    for (int i = 0; i < numRows; i++)
//    {
//        vector<int> a;
//        a.resize(i + 1, 1);
//        for (int j = 1; j < i ; j++)
//        {
//            a[j] = aa[i - 1][j] + aa[i - 1][j - 1];
//        }
//        aa.push_back(a);
//    }
////}
//int main()
//{
//    vector<int> nums = { 1, 1, 2 };
//    int i = 0;
//    while (1)
//    {
//        if (i == nums.size()-1)
//            break;
//        else if (nums[i] == nums[i + 1])
//        {
//            nums.erase(nums.begin() + i + 1);
//        }
//        else
//            i++;
//    }
//    


//int main()
//{
//    vector<int>numbers{ 1,2,3,2,2,2,5,4,2 };
//    //vector<int> a;
//    //a.resize(numbers.size(), 0);
//    //for (int i = 0; i < numbers.size(); i++)
//    //{
//    //    for (int j = 0; j <= i; j++)
//    //    {
//    //        if (numbers[i] == numbers[j])
//    //        {
//    //            a[j]++;
//    //            break;
//    //        }
//    //    }
//    //}
//    //for (int i = 0; i < numbers.size(); i++)
//    //{
//    //    if (a[i] > numbers.size() / 2)
//    //        cout<<numbers[i];
//    //}
//    int cond = -1;
//    int cnt = 0;
//    for (int i = 0; i < numbers.size(); ++i) {
//        if (cnt == 0) {
//            cond = numbers[i];
//            ++cnt;
//        }
//        else {
//            if (cond == numbers[i]) ++cnt;
//            else --cnt;
//        }
//
//    }
//    cnt = 0;
//    for (const int k : numbers) {
//        if (cond == k) ++cnt;
//    }
//    if (cnt > numbers.size() / 2) return cond;
//    return 0;
//}
//vector<string> str{ "","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz" };
//
//void CB(string& digits, string comstr, vector<string>& v, int level) {
//    if (level == digits.size())
//    {
//        v.push_back(comstr);
//        return;
//    }
//    int n = digits[level] - '0';
//    string st = str[n];
//    for (int i = 0; i < st.size(); i++)
//    {
//        CB(digits, comstr+st[i], v, level+1);
//    }
//}
//
//int main()
//{
//    string d="23";
//    vector<string> v;
//    CB(d, "", v, 0);
//    for (auto a : v)
//    {
//        cout << a<<" ";
//    }
//
//	return 0;
//}
//
//int singleNumber(vector<int>& nums) {
//    int ans = 0;
//    for (int i = 0; i < 32; ++i) {
//        int total = 0;
//        for (int num : nums) {
//            total += ((num >> i) & 1);
//        }
//        if (total % 3) {
//            ans |= (1 << i);
//        }
//    }
//    return ans;
//}




//
//
//
//
//int main()
//{
//    vector<int>a{ 1,2,3,2,2,3,1,3,7,1 };
//    cout<<singleNumber(a);
//	return 0;
//}

#include<stack>

//class MinStack {
//public:
//    MinStack() {
//
//    }
//
//    void push(int val) {
//        st1.push(val);
//        if (st2.size())
//        {
//            if (st2.top() >= val)
//            {
//                st2.push(val);
//            }
//
//        }
//        else
//            st2.push(val);
//
//    }
//
//    void pop() {
//        int a=st1.top();
//        st1.pop();
//        if (a == st2.top())
//        {
//            st2.pop();
//        }
//
//    }
//
//    int top() {
//        return st1.top();
//    }
//
//    int getMin() {
//        return st2.top();
//    }
//private:
//    stack<int> st1;
//    stack<int> st2;
//
// 
// 
// 
// };

class Solution {
public:

    bool IsPopOrder(vector<int>& pushV, vector<int>& popV) {
        stack<int> st1;
        int pushi = 0, popi = 0;
        while (pushi<pushV.size())
        {
            st1.push(pushV[pushi++]);
            while(!st1.empty()&&st1.top() == popV[popi])
            {
                st1.pop();
                popi++;
            }
        }
        return st1.empty();
    }
};
















